package com.atguigu.sort;

import java.util.Arrays;

/**
 * @author shengxiao
 * @date 2021/7/22 13:12
 *
 *  归并排序（Merge sort）:
 *      是建立在归并操作上的一种有效的排序算法，归并排序对序列的元素进行逐层折半分组，
 *      然后从最小分组开始比较排序【按照升序排列】，合并成一个大的分组，逐层进行，最终所有的元素都是有序的。
 *      注意：最小分组本来就是已经排好序的，不论是从大到小还是从小到大都是如此，故可直接回溯到前一个调用点，继续对倒数第二小的分组进行合并。
 *
 *         // 注意：递归不要 被绕晕了，主要是回溯的思想比较复杂，你可以宏观看一下，是先向左递归，然后再向右递归 ，然后再合并；
 *         // 而其内部的调用很复杂，但始终每一个递归栈中的这三个递归方法，都是在为每一组合并的进行按序服务；
 *         // 你可以看看我在快排QuickSort2 里面对具体递归中方法的如何调用分析了一个层面；不要陷得太深，具体的思路理解就好。
 */
public class MergeSortDemo {

    public static void main(String[] args) {
        int[] arr = {8,4,5,7,1,3,6,2} ;

        // 注意：temp数组其实可以只定义一个，然后共享，因为我们对每一层的合并的元素，都是对在 left和right为边界下进行的，
        // 所以，我们只需要确定在这个区域下已经归并排序成功，就可以了，
        // 而temp数组在每一层都是需要重新覆盖要合并的数组，而且
        // temp数组的作用：
        //  1. 作为每一层 中 对于 对应的组的 合并 在 left和right下的进行存放。
        //  2. 我们在处理完每一层后无需恢复现场。即无需重置，因为这里是通过 "覆盖+边界" 来对原数组arr进行合并。这和处在第几层毫无影响。
        int[] temp = new int[arr.length] ;

        // 递归入口
        mergeSort(arr, 0, arr.length - 1, temp);
        System.out.println(Arrays.toString(arr));
    }

    /**
     *
     * @param arr   排序的原始数组
     * @param left  左边有序序列的初始索引
     * @param right 右边末尾元素的索引
     * @param temp  做中转的数组，最后修改后的元素还要再次拷贝回原数组arr
     *
     */
    public static void mergeSort(int[] arr,int left, int right,int[] temp){

        // why？？？
        // 因为当只剩下一个元素的时候，原始的序列已然被分解为一个元素一组
        // 且：当前只是在探测 只剩下一个元素的下一层 递归是否满足。
        // 即此时left == right，而此时每一个组的元素默认都是一组，而且是不能再分解了
        //所以递归退层，返回到只剩下一个元素的那一层递归栈。然后就可以进行合并了
        if(left == right){
            return ;
        }

        // 而且你有没有注意到：
        // 1.如果序列中有偶数个元素，则左右序列元素一致，且 mid指针指向左序列的最后一个元素的位置，那么右序列的第一个位置就是mid+1
        // 2.如果序列中有奇数个元素，则左右序列元素不一致，则一般来说：我们都会以左大右小的序列，因此左序列会比右序列元素大1，而mid指针也是指向左序列的最后一个位置，那么右序列的第一个位置就是mid+1

        // 而且为什么可以保证各个递归栈中的变量不会相互干扰，这是使用了基本数据类型，在栈中是不会共享的。

        int mid = (left + right) / 2 ;  // 向下取整，在这题比较适用，尤其是奇偶数个元素

        mergeSort(arr, left, mid, temp);   // 往左递归

        mergeSort(arr, mid + 1, right, temp);   // 往右递归

        merge(arr,left,mid,right, temp) ;   // 合并

    }

    /**
     *
     * @param arr
     * @param left
     * @param mid
     * @param right
     * @param temp
     *
     * 为什么需要这几个参数,why???
     * 首先，你如果想要合并，那你是不是需要世道当前层的left，mid，right，来确定边界值
     * 以及原始的数组arr，和要保存到的临时数组temp【因为在原数组修改太麻烦了，可能还不如直接开辟一个数组【共享临时数据】】
     * 然后将修改的结果再覆盖到原数组arr【这里也有一个坑：不能直接覆盖】
     * 如果直接覆盖的话，会将temp中的一些没有赋值的，即初始值0 将原数组arr中一些没有排序过的元素值 进行覆盖，导致后面的快排后，得到很多个0
     *
     * 注意：如果是在归并排序的过程中，如果是排当前层，那么就对当前层排序完毕，而上层未排序的元素还是没动。
     */
    public static void merge(int[] arr,int left,int mid,int right,int[] temp){

        // 这里千万不要将边界值拿去遍历，一定要用辅助指针i,j来遍历，不然到时候，当前层的排序可能就无效了。

        int i = left ;  // 初始化i，左边有序序列的初始索引
        int j = mid + 1 ;   // 初始化j，右边有序序列的初始索引 ，
        int t = 0 ; // temp数组的记录合并过程中，指针的变化情况，并无实际作用，好像只是作为一个索引，进行遍历添加元素

        int p = 0 ; // 原数组arr经过分解后，要合并的组，需要记录对应的左右边界，则就是当前层的left和right决定
                    // 而temp数组对应的记录合并时候排序完的当前层的元素。而上面的指针t只是作为一个索引，进行遍历添加元素
                    // 因此指针p也是作为temp的一个索引，进行遍历获取元素值然后覆盖到 原数组arr在合并的组中。

                    // 综上：指针t 和 指针p 没有什么差别，但这里为了进行区分，所以我定义了两个变量

        //（一）
        // 先把左右两边（有序）的数据按照规则填充到temp数组
        // 直到左右两边的有序序列，有一边处理完毕为止,然后将另一边按照顺序再依次填充
        // 最后将temp数组拷贝到原始数组arr
        while(i <= mid && j <= right){

            if(arr[i] < arr[j]){
                temp[t] = arr[i] ;
                i ++ ;
                t ++ ;
            }else {
                temp[t] = arr[j] ;
                j ++ ;
                t ++ ;
            }
        }

        //（二）
        // 把有剩余数据的一边的数据依次全部填充到temp
        while(i <= mid){    // 说明左边的序列还有剩余数据
            temp[t] = arr[i] ;
            i ++ ;
            t ++ ;
        }
        while(j <= right){
            temp[t] = arr[j] ;
            j ++ ;
            t ++ ;
        }

        // （三）
        // 将temp数组的元素拷贝到arr
        // 注意：并不是每次都拷贝所有的元素，对于不同的分组，存在不同的拷贝方法，每一次的拷贝方法只是针对当前合并的分组而言，
        // 每次合并都是合并完才执行下一次合并函数，所以上一次合并的数组已经释放了，即当每一次临时数组合并完之后都会进行释放空间

        //

        // 注意：left边界指针不能移动，所以只能定义一个辅助指针tempLeft来进行遍历
        int tempLeft = left ;

        while(tempLeft <= right){

            arr[tempLeft] = temp[p] ;
            p++ ;
            tempLeft++ ;
        }

    }
}
